/******************************************************************************
** 
** Shell sort.
** 
** File name:	shellsort.c
** Compilation:	cc shellsort.c -o shellsort
** Execution:	./shellsort
** 
** Description:
** D.L.Shell sorting algorithm.
** 
******************************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define N_ELEM 20

int main()
{
    int data[N_ELEM];
    int i, j, gap, temp;

    printf("RAND_MAX=%d\n", RAND_MAX);
    srand(0);
    printf("Before sort:\n");
    for (temp = 0; temp < N_ELEM; temp++) {
        data[temp] = rand()/10000000;
        printf("%d%c", data[temp], ((temp+1)%10) ? '\t' : '\n');
    }
    
    for (gap = N_ELEM/2; gap > 0; gap /= 2) {
        for (i = gap; i < N_ELEM; i++) {
            for (j = i-gap; (j >= 0) && (data[j] > data[j+gap]); j -= gap) {
                temp = data[j];
                data[j] = data[j+gap];
                data[j+gap] = temp;
            }
        }
        printf("Gap = %d:\n", gap);
        for (temp = 0; temp < N_ELEM; temp++) {
            printf("%d%c", data[temp], ((temp+1)%10) ? '\t' : '\n');
        }
    }

    printf("After the sort:\n");
    for (temp = 0; temp < N_ELEM; temp++) {
        printf("%d%c", data[temp], ((temp+1)%10) ? '\t' : '\n');
    }

    return 0;
}

